package sort;

/**
 * @author zxl
 * @version 1.0
 * @date 2021/12/5 12:24
 * 归并排序    将当前序列进行拆分 ，直到拆分成不可在分，然后将拆分的元素进行有序组合
 */
public class MergeSorting {

    /**
     * 左边复制的数组
     */
    private static int[] leftArray;

    static int[] a = new int[]{1,2,3,4,5,6,7,8,9};

    public static void main(String[] args) {
        leftArray = new int[(a.length >> 1)];
        sort(0,a.length);
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    /**
     * 递归，将序列拆分
     * @param begin
     * @param end
     */
    public static void sort(int begin ,int end){
        if(end - begin < 2) {
            return;
        }
        int mid = (end + begin) >> 1;
        sort(begin,mid);
        sort(mid,end);
        merge(begin,mid,end);
    }

    /**
     * 和并
     * @param begin
     * @param mid
     * @param end
     */
    private static void merge(int begin, int mid, int end) {
        //左边数组索引
        int li = 0;
        //左边数组长度
        int le = mid - begin;
        //右边数组索引
        int ri = mid;
        //右边长度
        int re = end;
        //当前复制位置索引
        int ai = begin;
        
        //复制左边数组
        for (int i = li; i < le; i++) {
            //从当前数组的位置进行复制  所以为begin+i
            leftArray[i] = a[begin+i];
        }

        // 判断  左边未结束
        while (li < le){
            //当左边的数小于右边的数  将新数组的数赋值到原数组的左边位置
            if(ri < re && leftArray[li] < a[ri]){
                a[ai++] = leftArray[li++];
            //将原数组右边的数赋值到原数组左边的位置
            }else{
                a[ai++] = a[ri++];
            }
        }
    }
}
